@article{Franceschini:2005:ISO:1082036.1082037,
 author = {Franceschini, Gianni and Geffert, Viliam},
 title = {An In-place Sorting with O(Nlog N) Comparisons and O(N) Moves},
 journal = {J. ACM},
 issue_date = {July 2005},
 volume = {52},
 number = {4},
 month = jul,
 year = {2005},
 issn = {0004-5411},
 pages = {515--537},
 numpages = {23},
 url = {http://doi.acm.org/10.1145/1082036.1082037},
 doi = {10.1145/1082036.1082037},
 acmid = {1082037},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Sorting in-place}
,abstract = {We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(nlog n) element comparisons and O(n) element transports.This solves a long-standing open problem, stated explicitly, for example, in Munro and Raman [1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.}
}